7 |
您所在的位置：网站首页 › 表达式3 or5 › 7 |
|
此题为离开栈的新手村后，第一个挑战性大的题目。 修改提交20余次，本地编译器上多次执行，最终成品。 书接上文，你已经学会了栈的基本操作，现在来挑战一下栈的简单习题吧（迫真） 题目与分析：算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。 输入格式:输入在一行中给出不含空格的中缀表达式，可包含+、-、*、/以及左右括号()，表达式不超过20个字符。 输出格式:在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。 输入样例: 2+3*(7-4)+8/4 输出样例: 2 3 7 4 - * + 8 4 / + 代码分析： 1.鸿蒙初开：这里的栈包含了数字栈和字符栈，数字栈是因为我起初认为输入数字直接打印便可，后发现不行之后，加入，与传统栈的定义有出入，属于是即兴发挥。 全局变量flag为检测括号是否打不打，与入栈时候，以及打印空格的操作联系密切； bracket变量为检测括号变量； NumTop是数字栈顶，NumFront是数字栈底。 int flag = 0; //打空格问题 typedef struct{ //定义栈 char data[MAXSIZE]; int top; int bracket; char num[MAXSIZE]; int NumTop; int NumFront; }Stack; void InitStack(Stack *S){ //构造新栈 S->top = -1; S->NumTop = 0; S->NumFront = 0; S->bracket = 0; } 2.栈的基础操作：SymJudge判断字符优先级，Pop出栈，Push入栈（改动极大，主要分为了数字，四则运算，括号三个部分），由Push调用Pop和SymJudge。 置空读取，为事后结束入栈后，打印出剩下的符号。 char SymJudge(char ch,char fch){ if((ch == '*' || ch == '/') && (fch == '+' || fch == '-')) return ''; if((ch == '*' || ch == '/') && (fch == '*' || fch == '/')) return '='; if((ch == '+' || ch == '-') && (fch == '+' || fch == '-')) return '='; return '='; } void Pop(Stack *S){ //运算符出栈 if(S->top == -1) printf("栈为空，无法出栈"); char ele; ele = S->data[S->top]; S->top--; if(ele != '(') printf("%c ",ele); } void Push(Stack *S, char e){ //入栈 if((e >= '(' && e NumFront < S->NumTop){ printf("%c",S->num[S->NumFront]); S->NumFront++; } if(flag == 1) { printf(" "); flag = 0; } if(e >= '*') { if (S->top == -1 || S->bracket == 1){ //有括号时 if((S->NumTop == 0) || ((S->data[S->top] == '(') &&(S->bracket != 2))) { if(e == '+') return; else if(e == '-') { S->num[S->NumTop] = e; S->NumTop++; return; } } else{ S->top++; S->data[S->top] = e; } return; } if (S->top >= 0) { switch (SymJudge(e, S->data[S->top])) { case '':{ Pop(S); while (S->top > -1 && (SymJudge(e, S->data[S->top]) == '>' || SymJudge(e, S->data[S->top]) == '=') && S->data[S->top] !='(') { Pop(S); } S->top++; S->data[S->top] = e; break; } case '=': { if(S->bracket == 1) { S->num[S->NumTop] = e; S->NumTop++; } else{ S->top++; S->data[S->top] = e; } break; } } } } if(e top++; S->data[S->top] = e; S->bracket = 1; } if(e == ')'){ while (S->data[S->top] != '('){ Pop(S); } S->top--; S->bracket = 0; } } } if((e >= '1' && e num[S->NumTop] = e; S->NumTop++; flag = 1; S->bracket = 2; return; } } void Print(Stack* S){ //置空读取 while(S->top != -1) { if(S->top > 0) printf("%c ", S->data[S->top]); else printf("%c", S->data[S->top]); S->top--; } } 3.主函数 —— 启动！：因为要求输入在一行，如果一个一个字符输入，会有回车的风险，所以先安排一个string来接受输入，然后将其的字符一个一个Push检查，且很方便的知道循环几次，这里需要引用string.h头文件。主要留意一下空格的打印问题，本代码打印问题未做简洁处理，分散在主函数、Push、Pop、Print中，非常需要注意。 int main(){ Stack stk; InitStack(&stk); char s[21]; scanf("%s",s); int l = strlen(s); int size = 0; for(int i = 0;itop = -1; S->NumTop = 0; S->NumFront = 0; S->bracket = 0; } char SymJudge(char ch,char fch){ if((ch == '*' || ch == '/') && (fch == '+' || fch == '-')) return ''; if((ch == '*' || ch == '/') && (fch == '*' || fch == '/')) return '='; if((ch == '+' || ch == '-') && (fch == '+' || fch == '-')) return '='; return '='; } void Pop(Stack *S){ //运算符出栈 if(S->top == -1) printf("栈为空，无法出栈"); char ele; ele = S->data[S->top]; S->top--; if(ele != '(') printf("%c ",ele); } void Push(Stack *S, char e){ //入栈 if((e >= '(' && e NumFront < S->NumTop){ printf("%c",S->num[S->NumFront]); S->NumFront++; } if(flag == 1) { printf(" "); flag = 0; } if(e >= '*') { if (S->top == -1 || S->bracket == 1){ //有括号时 if((S->NumTop == 0) || ((S->data[S->top] == '(') &&(S->bracket != 2))) { if(e == '+') return; else if(e == '-') { S->num[S->NumTop] = e; S->NumTop++; return; } } else{ S->top++; S->data[S->top] = e; } return; } if (S->top >= 0) { switch (SymJudge(e, S->data[S->top])) { case '':{ Pop(S); while (S->top > -1 && (SymJudge(e, S->data[S->top]) == '>' || SymJudge(e, S->data[S->top]) == '=') && S->data[S->top] !='(') { Pop(S); } S->top++; S->data[S->top] = e; break; } case '=': { if(S->bracket == 1) { S->num[S->NumTop] = e; S->NumTop++; } else{ S->top++; S->data[S->top] = e; } break; } } } } if(e top++; S->data[S->top] = e; S->bracket = 1; } if(e == ')'){ while (S->data[S->top] != '('){ Pop(S); } S->top--; S->bracket = 0; } } } if((e >= '1' && e num[S->NumTop] = e; S->NumTop++; flag = 1; S->bracket = 2; return; } } void Print(Stack* S){ //置空读取 while(S->top != -1) { if(S->top > 0) printf("%c ", S->data[S->top]); else printf("%c", S->data[S->top]); S->top--; } } int main(){ Stack stk; InitStack(&stk); char s[21]; scanf("%s",s); int l = strlen(s); int size = 0; for(int i = 0;i |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |